1. Field of the Invention
The present invention relates to the generation of pseudo-random numbers used in controlling nodes of communications systems or other systems involving shared resources; and particularly to determine the length of backoff intervals in CSMA/CD networks.
2. Description of Related Art
Network nodes in a CSMA/CD (Carrier Sense Multiple Access with Collision Detection) system, such as 802.3 CSMA/CD systems ("Ethernet"), are required to generate pseudo-random numbers as part of the collision recovery process. Simply put, when two or more nodes collide, they each generate a pseudo-random number which determines the integral number of slot-times that the node will wait (backoff) before attempting to retransmit. If two nodes generate the same number, they will retransmit at the same time, causing another collision, pseudo-random number generation, and backoff.
Theoretically, the nodes will eventually generate distinct numbers and one of the nodes (the one with the lower pseudo-random number) will be able to transmit successfully. The 802.3 specification places an upper limit of 16 attempts on a transmission before it is aborted. From a channel utilization standpoint, is desirable that the two nodes generate distinct numbers in as few attempts as possible.
There are a number of methods that allow a single node to generate pseudo-random numbers through time. However, it has proven more difficult to arrive at a solution that, when duplicated within several nodes on a network, will allow those nodes to generate pseudo-random numbers independently of one another. This is necessary to avoid having two nodes backoff in look-step.
Consider the case of two identical nodes on a network, as shown in FIG. 1. Node A 10 and node B are two adjacent nodes on a network 12. For the sake of simplicity, we will assume that there is zero node-to-node propagation delay.
Both nodes are initialized and begin operating at time zero as indicated along trace 13. At time t.sub.0 they start transmitting 14, they both detect that a collision is occurring at time t.sub.1, and each generates a pseudo-random number to determine the backoff interval. Since both nodes A and B were initialized at the same time, and they detected a collision at the same time, they could produce the same pseudo-random number, causing another collision at time t.sub.2 after the backoff interval 15. This could continue through all 16 attempts in an 802.3 network until the transmissions are aborted.
The problem can be generalized as this: given two nodes in a network whose pseudo-random number generators are operating in lock-step, an algorithm must be chosen to force the two nodes to diverge and produce distinct numbers.
Several companies have implemented integrated 802.3 controllers. They each have had to deal with the pseudo-random number generation problem.
The Intel 82586 and National Semiconductor 8390 are representative. In the 82586, a cyclic redundancy code CRC generated from the last frame transmission is used as the pseudo-random number. There is a substantial chance that two nodes could generate the same CRC value from different transmitted frames. However, as two nodes repeatedly collide, the chance that they would repeatedly generate the same CRC gets progressively smaller.
In the 8390, National has implemented a free-running oscillator which is sampled with the 10 MHz network clock. The sampled bits are assembled, probably by shifting them into a shift register, to form the required width for use by the backoff algorithm. There is a significant probability that a specific collision will cause two nodes to "roll" the same number, but as in the Intel case, this probability becomes increasingly small over repeated collisions.
An early version of the Intel 82586 used a pseudo-random number generation algorithm based on a free-running 10-bit counter, operating off the 10 MHz network clock. This method was abandoned because multiple nodes on a network could have their counters in synchronism, causing repeated collisions.
Accordingly, it is desirable to provide a pseudo-random number generator for use in controlling nodes of a communication network that minimizes the possibility of having pseudo-random number generators at two nodes in the network operating in lock-step. This is particularly important in high traffic CSMA/CD networks, such as the 802.3 standard.